// https://leetcode.cn/problems/longest-valid-parentheses/
// 法一：动态规划

// class Solution {
// public:
//     int longestValidParentheses(string s) {
//         vector<int> rec(s.length(), 0);
//         int maxLen = 0;
//         for (int i = 1; i < s.length(); ++i) {
//             if (s[i] == ')') {
//                 if (s[i - 1] == '(')
//                     rec[i] = (i > 1?rec[i - 2]:0) + 2;
//                 else if (i >= rec[i - 1] + 1 && s[i - rec[i - 1] - 1] == '(') 
//                     rec[i] = rec[i - 1] + ((i - rec[i - 1]) >= 2? rec[i - rec[i - 1] - 2]:0) + 2; // 注意
//             maxLen = max(maxLen, rec[i]);
//             }
//         }
//         return maxLen;
//     }
// };

// 法二：栈，存放左括号和最后一个未匹配的右括号
// class Solution {
// public:
//     int longestValidParentheses(string s) {
//         int maxLen = 0;
//         stack<int> stk;
//         stk.push(-1);
//         for (int i = 0; i < s.length(); ++i) {
//             if (s[i] == '(') stk.push(i);
//             else {
//                 stk.pop();
//                 if (stk.empty()) {
//                     stk.push(i);
//                 } else {
//                     maxLen = max(maxLen, i - stk.top());
//                 }
//             }
//         }
//         return maxLen;
//     }
// };

// 法三：贪心
// 每当 left 计数器与 right 计数器相等时，计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。
// 会漏掉一种情况：遍历的时候左括号的数量始终大于右括号的数量，从右往左再遍历一次
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') left++;
            else right++;
            if (right > left) {
                left = 0;
                right = 0;
            } else if (right == left) {
                maxLen = max(maxLen, left * 2);
            }
        }
        left = 0;
        right = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            if (s[i] == '(') left++;
            else right++;
            if (left > right) {
                left = 0;
                right = 0;
            } else if (right == left) {
                maxLen = max(maxLen, left * 2);
            }
        }
        return maxLen;
    }
};
